// Created by WXX on 2022/2/3 17:33
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：4 ms, 在所有 C++ 提交中击败了46.67%的用户
 * 内存消耗：6.2 MB, 在所有 C++ 提交中击败了61.33%的用户
 */
class Solution {
public:
    int findMinFibonacciNumbers(int k) {

        vector<int> nums;
        int a = 1, b = 1, c = 1;
        while (c <= 1e9) {
            nums.push_back(c);
            a = b;
            b = c;
            c = a + b;
        }

        int res = 0;
        for (int i = nums.size() - 1; i >= 0; i--)
            if (k >= nums[i]) {
                k -= nums[i];
                res++;
            }

        return res;
    }
};

int main() {

    cout << Solution().findMinFibonacciNumbers(7) << endl;  // 2
    cout << Solution().findMinFibonacciNumbers(10) << endl;  // 2
    cout << Solution().findMinFibonacciNumbers(19) << endl;  // 3

    return 0;
}
